#include <stdio.h>
#include <stdlib.h>
#define MaxQueue 20

typedef struct node
{
	int name;//1,2,3
	struct node * next;
}Node;

typedef struct edge
{
	int start,end;
}Edge;

typedef struct queue 
{
	Node * q[MaxQueue];
	int head,tail;
}Queue;
void initNodes(Node * nodes[]){
	for(size_t i = 1;i < 8; ++i){
		Node * node = (Node*)malloc(sizeof(Node));
		node->name = i;
		node->next = NULL;
		nodes[i] = node;
	}
}
Edge * createEdge(int start, int end){
	Edge * edge = (Edge*)malloc(sizeof(Edge));
	edge->start = start;
	edge->end = end;
	return edge;
}
void intiEdges(Edge* edges[]){

	edges[0] = createEdge(3,1);
	edges[1] = createEdge(3,6);
	edges[2] = createEdge(1,2);
	edges[3] = createEdge(1,4);
	edges[4] = createEdge(2,4);
	edges[5] = createEdge(2,5);
	edges[6] = createEdge(4,3);
	edges[7] = createEdge(4,5);
	edges[8] = createEdge(4,6);
	edges[9] = createEdge(4,7);
	edges[10] = createEdge(5,7);
	edges[11] = createEdge(7,6);
}
void createAdjList(Node * nodes[],Edge * edges[]){
	initNodes(nodes);
	intiEdges(edges);
	for(size_t i = 1; i < 8; ++i){
		Node * temp = nodes[i];
		for(size_t j = 0; j < 12; ++j){
			if(edges[j]->start==nodes[i]->name){
				Node * node = (Node*)malloc(sizeof(Node));
				node->name = edges[j]->end;
				node->next = NULL;
				temp->next = node;
				temp=node;
			}
		}
	}
}
Queue * initQueue(){
	Queue * q = (Queue*)malloc(sizeof(Queue));
	q->head = 0;
	q->tail = 0;
	return q;
}
void addQueue(Queue * queue, Node * node){
	if(queue->tail < MaxQueue){
		queue->q[queue->tail++] = node;
	}
}
Node * popQueue(Queue * queue){
	if(queue->head!=queue->tail)
		return queue->q[queue->head++];
	return NULL;
}
int isEmpty(Queue * queue){
	if(queue->head==queue->tail)
		return 1;
	return 0;
}
void findMinPath(Node * nodes[],Node * start,int dist[],int path[]){
	dist[start->name] = 0;
	path[start->name] = start->name;
	Queue * queue = initQueue();
	addQueue(queue,start);
	while(isEmpty(queue)!=1){
		Node * node = popQueue(queue);
		Node * temp = node->next;
		while(temp!=NULL){
			if(dist[temp->name]==-1){
				path[temp->name] = node->name;
				dist[temp->name] = dist[node->name] + 1;
				addQueue(queue,nodes[temp->name]);
			}
			temp=temp->next;
		}
	}
}
int main()
{
	Node * nodes[8];
	Edge * edges[12];
	createAdjList(nodes,edges);
	for(size_t i = 1; i < 8; i++){
		Node * temp = nodes[i];
		while(temp){
			printf("%d-",temp->name );
			temp=temp->next;
		}
		printf("\n");
	}
	int dist[8]={-1,-1,-1,-1,-1,-1,-1,-1};
	int path[8];
	findMinPath(nodes,nodes[4],dist,path);
	for (int i = 1; i < 8; ++i)
	{
		printf("%d节点到源点4的距离是%d，需要经过的前一个节点为%d\n",i,dist[i],path[i]);
	}
	return 0;
}